package com.whitedust.top100;

/**
 *
 * @author A
 * @since 2025/11/17 19:13
 */

public class Top100 {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        //全部构成一个最大堆
        heapify(nums);
        for (int end = n - 1; end >= 1; ) {
            //将最大数放到末尾
            swap(nums, 0, end);
            end--;
            //去除掉排好序的一个数再执行构建最大堆
            siftDown(nums, 0, end);
        }
        return nums;
    }

    private void heapify(int[] nums) {
        int n = nums.length;
        //从最后一个非叶子节点开始倒序保证最大堆
        for (int i = (n - 2) / 2; i >= 0; i--) {
            siftDown(nums, i, n - 1);
        }
    }

    // k表示从这个节点开始保证最大堆
    private void siftDown(int[] nums, int k, int end) {
        // 2 * k + 1 计算左孩子节点下标
        while (2 * k + 1 <= end) {
            int j = 2 * k + 1;
            // 寻找左右孩子节点中更大那一个的下标
            if (j + 1 <= end && nums[j + 1] > nums[j]) {
                j++;
            }
            // 孩子节点大则互换
            if (nums[j] > nums[k]) {
                swap(nums, j, k);
            } else {
                break;
            }
            //因为产生交换，所以交换后的子节点需要更新堆状况
            k = j;
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
